#include "struct.h"

void swap(CODING *p, CODING *q ) {
    CODING temp;
    temp = *p;
    *p = *q;
    *q = temp;
    return;
}

void swap2(LINE *p, LINE *q) {
    LINE temp;
    temp = *p;
    *p = *q;
    *q = temp;
    return;
}

void quickSort( CODING *content, int qlen ) {
    int j = 0, i, max = qlen, change = 1;
    stack *head, *p, *tempStack;
    head = (stack *)malloc(sizeof(stack));
    head->top = NULL;
    p = head;
    CODING temp;
    if( qlen == 1 ) { return; }
    while( j < qlen - 1 ) {
        for( i = j + 1; i < max; i++ ) {
            if( content[i].charFreq.freq < content[j].charFreq.freq ) {
                swap(content + j + change, content + i);
                change++;
            }
        }
        if( change == 2 && j + 1 <= qlen ) {
            swap(content+j, content+j+change-1);
            j = j + 2;
            change = 1;
        } else if( change > 2 ) {
            swap(content+j, content+j+change-1);
            stack a;
            a.num = p->num;
            a.top = p;
            *p = a;
            change = 1;
        } else {
            j++;
        }
        while( j >= max - 1 && max < qlen ) {
            tempStack = (*p).top;
            free(p);
            if( (*tempStack).top == NULL ) {
                max = qlen;
                p = head;
            } else {
                p = tempStack;
                max = (*p).num;
            }
        }
    }
}

void boob(int index, LINE *charTree, int qlen) {
    int i = 0;
    for( i = index; i < qlen - 1; i++ ) {
        if( charTree[i].tar->charFreq.freq > charTree[i + 1].tar->charFreq.freq ) {
            swap2(charTree + i, charTree + i + 1);
        } else {
            return;
        }
    }
}

void show( CODING *p, int deep, char *codes, int direct ) {
    if( p == NULL ) {
        return;
    }
    if( direct == 1 ) {
        codes[deep] = '0';
    }
    if( direct == 2 ) {
        codes[deep] = '1';
    }
    char *codetemp = (char *)calloc(sizeof(char), deep + 1);
    strncpy(codetemp, codes + 1, deep);
    p->code = codetemp;
    show( (*p).leftChild, deep + 1, codes, 1 );
    show( (*p).rightChild, deep + 1, codes, 2 );
    return;
}

CODING *createHaffmanCode( TEXT *charFreq, int len, int ret ) {
    CODING *charTree = (CODING *)calloc(sizeof(CODING), len);
    LINE *fake = (LINE *)calloc(sizeof(LINE), len);
    int i = 0;
    for( i; i < len; i++) {
        charTree[i].charFreq = charFreq[i];
        charTree[i].leftChild = NULL;
        charTree[i].rightChild = NULL;
        charTree[i].code = NULL;
    }
    quickSort(charTree, len);
    for( i = 0; i < len; i++) {
        fake[i].tar = charTree + i;
    }
    CODING *charStore;
    charStore = charTree;
    int index = 0;
    while(index < len - 1) {
        CODING *tempChar = (CODING *)malloc(sizeof(CODING));
        tempChar->leftChild = (fake + index)->tar;
        tempChar->rightChild = (fake + index + 1)->tar;
        tempChar->charFreq.charbody = '\0';
        tempChar->charFreq.freq = fake[index].tar->charFreq.freq + fake[index + 1].tar->charFreq.freq;
        (fake + index + 1)->tar = tempChar;
        index++;
        boob( index, fake, len );
    }
    int deep = 0;
    char *codes = (char *)calloc(sizeof(char),len);
    show((fake + len - 1)->tar, deep, codes, 0);
    free(codes);
    if( ret == 1) {
        return charTree;
    } else {
        return (fake + len - 1)->tar;
    }
}